'''
Created on Sep 14, 2011

@author: nktran
'''

import re
import utils

from table import Table
from fsa import FSA
from constant import ALPHABET_FILE, INSTANCE_FILE, LAMBDA, QUERY_FILE,\
    TABLE_FILE

class Angluin:
    """
    Learning grammar using Angluin algorithm
    Automatically answer membership queries and counter-examples
    1. For membership queries:
        @return: True if the query is in the instance file
    2. For counter-example:
        @return: example in the instance file that is not accepted by acceptor
        @improve: using negative examples to adjust acceptor    
    """
    
    def __init__(self):
        """
        Default constructor
        
        @var alphabet: contains alphabet of unknown grammar
        @var instance: contains examples provided for answering quries
        @var query: store all asked queries
        @var table: Table object    
        """
        self.alphabet = set()
        self.instance = set()
        self.query = dict()
        self.table = Table()
        
        self.debug = True
        
    def init_alg(self, ext):
        """
        Initialize variables
        
        Adding lambda into prefix and suffix set
        Asking membership queries {lambda, char in alphabet} and add to the table
        
        @param ext: file extension 
        """
        self.set_instance(ext)
        self.set_alphabet(ext)
        
        self.table.add_to_prefix([LAMBDA])
        self.table.add_to_suffix([LAMBDA])
        
        answer = self.ask_query('_lambda_',ext)
        self.table.update_cell(LAMBDA, LAMBDA, answer)
        self.query[LAMBDA] = answer
        
        for char in self.alphabet:
            answer = self.ask_query(char,ext)
            self.table.update_cell(char, LAMBDA, answer)
            self.query[char] = answer        

    def set_alphabet(self, ext):
        """
        @return: alphabet from the file
        """
        fname = ALPHABET_FILE + ext
        self.alphabet = utils.read_file(fname,'\s+')   

    def set_instance(self, ext):
        """
        @return: instances from the file
        """
        fname = INSTANCE_FILE + ext
        self.instance = utils.read_file(fname,'\n')        
    
    def learn(self, ext):
        """
        Learn finite state automata that accept an unknown regular language
        using an oracle to answer membership queries and counter example
        
        @param: file extension
        @return: acceptor        
        """
        self.init_alg(ext)
        num_tab = 0
        while True:
            new_suffix_item = self.table.find_new_suffix(self.alphabet)
            new_prefix_item = self.table.find_new_prefix(self.alphabet)
            
            while new_suffix_item != None or new_prefix_item != None:
                if new_suffix_item != None:
                    print "Table %d is not consistent!" % (num_tab) 
                    print "Adding %s into the suffix set!\n" % (new_suffix_item)
                    self.table.add_to_suffix([new_suffix_item])
                    self.update_suffix(set([new_suffix_item]),ext)

                    if self.debug:
                        log = "Table %d is not consistent!\n" % (num_tab)
                        log += "Adding %s into the suffix set!\n" % (new_suffix_item)
                        log += "Prefix: %s" % utils.toString(self.table.prefix)
                        log += "Suffix: %s" % utils.toString(self.table.suffix)
                        utils.log_file(QUERY_FILE+ext, log)
                        utils.log_file(TABLE_FILE+ext, "Table %d:\n%s" % 
                                       (num_tab, self.table.toString()))

                    num_tab = num_tab + 1
                        
                if new_prefix_item != None:
                    print "Table %d is not closed!" % (num_tab) 
                    print "Adding %s into the prefix set!\n" % (new_prefix_item)
                    
                    self.table.add_to_prefix([new_prefix_item])
                    self.update_prefix(set([new_prefix_item]),ext)

                    if self.debug:
                        log = "Table %d is not consistent!\n" % (num_tab)
                        log += "Adding %s into the suffix set!\n" % (new_suffix_item)
                        log += "Prefix: %s" % utils.toString(self.table.prefix)
                        log += "Suffix: %s" % utils.toString(self.table.suffix)
                        utils.log_file(QUERY_FILE+ext, log)
                        utils.log_file(TABLE_FILE+ext, "Table %d:\n%s" % 
                                       (num_tab, self.table.toString()))
                    
                    num_tab = num_tab + 1                    
                                                        
                new_suffix_item = self.table.find_new_suffix(self.alphabet)
                new_prefix_item = self.table.find_new_prefix(self.alphabet)

            print "Table %d is closed and consistent!" % (num_tab)                       
            acceptor = FSA()
            acceptor.construct(self.table, self.alphabet, ext)
            
            counter_example = self.find_counter_example(acceptor)
            print "Counter example: %s" %(counter_example)
            if counter_example == None:
                return acceptor

            if self.debug:
                log = "Table %d is closed and consistent!\n" % (num_tab)
                log += "Counter example: %s\n" %(counter_example)
                utils.log_file(QUERY_FILE+ext, log)
                utils.log_file(TABLE_FILE+ext, "Table %d:\n%s" % 
                               (num_tab, self.table.toString()))
            #main operation
            self.add_cx_to_table(counter_example,ext)
            num_tab = num_tab + 1
    
    def find_counter_example(self, acceptor):
        """
        @return: counter-example
        """
        for inst in sorted(self.instance):
            if not acceptor.parse(inst):
                return inst
        return None
    
    def add_cx_to_table(self, counter_example=None,ext=""):
        """
        Adding the counter example to the table
        @note: Adding all prefix and itself
        """
        if counter_example == None:
            return
        new_prefix_set = set()
        pre = ""
        for substr in re.split('\s+', counter_example):
            pre = pre + substr
            new_prefix_set.add(pre)

        if self.debug:
            log = "Adding %s into prefix set!\n" % (' '.join(new_prefix_set))
            utils.log_file(QUERY_FILE+ext, log)    

        #main operation
        self.table.add_to_prefix(new_prefix_set)
        self.update_prefix(new_prefix_set,ext)        
    
    def update_suffix(self, new_suffix_set,ext=""):
        """
        Update the table with a new suffix set
        @return: new table
        """
        for pre in self.table.prefix:
            # prefix
            for suf in new_suffix_set:
                answer = self.ask_query(pre+suf,ext)
                self.table.update_cell(pre, suf, answer)
                self.query[pre+suf] = answer
            # prefix + alphabet
            for a in self.alphabet:
                for suf in new_suffix_set:
                    answer = self.ask_query(pre+a+suf,ext)
                    self.table.update_cell(pre+a, suf, answer)
                    self.query[pre+a+suf] = answer
                    
    def update_prefix(self, new_prefix_set, ext=""):
        """
        Update the table with a new prefix set
        @return: new table        
        """
        for pre in new_prefix_set:
            # prefix
            for suf in self.table.suffix:
                answer = self.ask_query(pre+suf,ext)
                self.table.update_cell(pre, suf, answer)
                self.query[pre+suf] = answer
            # prefix + suffix
            for a in self.alphabet:
                for suf in self.table.suffix:
                    answer = self.ask_query(pre+a+suf,ext)
                    self.table.update_cell(pre+a, suf, answer)
                    self.query[pre+a+suf] = answer
                    
    def ask_query(self, query, ext=""):
        """
        Return 1 if the query belongs to the unkown grammar
        Otherwise return 0
        
        @param query: asking query 
        """
        if self.query.has_key(query):
            return self.query[query]
        
        answer = 0
        for inst in self.instance:
            if ''.join(re.split('\s+', inst)) == query:
                answer = 1
                break
        if self.debug:
            log = "query = %s \t\t in language = %s\n" % (query,
                                                    answer)
            utils.log_file(QUERY_FILE+ext, log)
                    
        return answer
                    